Algorithmically random sequence
part 8/27 · 44.9 KB total
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Martin-Löf–Chaitin Thesis. The mathematical concept of "Martin-Löf randomness" captures the intuitive notion of an infinite sequence being "random".
Church–Turing thesis. The mathematical concept of "computable by Turing machines" captures the intuitive notion of a function being "computable". Just as Turing-computability has many equivalent definitions, Martin-Löf randomness also has many equivalent definitions. See next section.
Three equivalent definitions
Martin-Löf's original definition of a random sequence was in terms of constructive null covers; he defined a sequence to be random if it is not contained in any such cover. Gregory Chaitin, Leonid Levin and Claus Peter Schnorr proved a characterization in terms of algorithmic complexity: a sequence is random if there is a uniform bound on the compressibility of its initial segments. Schnorr gave a third equivalent definition in terms of martingales. Li and Vitanyi's book An Introduction to Kolmogorov Complexity and Its Applications is the standard introduction to these ideas.
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────